﻿//853. 车队
//在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。
//给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里 / 小时)。
//一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。
//车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。
//即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。
//返回到达目的地的车队数量 。



class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed)
    {
        int n = position.size();
        vector<pair<int, int>> arr;
        for (int i = 0; i < n; i++)
        {
            arr.push_back({ position[i],speed[i] });
        }
        sort(arr.begin(), arr.end(), [](pair<int, int> a, pair<int, int> b)->bool { return a.first > b.first; });
        stack<pair<int, int>> sta;
        sta.push(arr[0]);
        for (int i = 1; i < n; i++)
        {
            double a = 1.0 * (target - sta.top().first) / sta.top().second;
            double b = 1.0 * (target - arr[i].first) / arr[i].second;
            if (a < b)
            {
                sta.push(arr[i]);
            }
        }
        return sta.size();
    }
};